package Text20;

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        while (n-- > 0) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            int m = scanner.nextInt();
            int[] x = new int[1];
            int[] y = new int[1];
            int d=exgcd(a, m, x, y);
            if(b%d!=0){
                System.out.println("impossible");
            }else {
                System.out.println((long)(b / d) * x[0]  % m);
            }
        }
    }
    private static int exgcd(int a, int b, int[] x, int[] y) {
        if (b==0){
            x[0]=1;
            y[0]=0;
            return a;
        }
        int ret=exgcd(b,a%b,y,x);
        y[0]-=a/b*x[0];
        return ret;
    }
}
